{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 11-12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZYAAAEZCAYAAAC0HgObAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAGttJREFUeJzt3X20XXV95/H3x5uAkSmEh6sDN7GJY8QJxknsIdrSZk2lSmgtSSlqqOXBWrFWZnRsacNMHdu0DrCYJY5rMVYU5KFAQISYqQ/RWai1rWBOSCQEiISIcG9QrhOCWFMg4TN/nH31cLkk5yS/e/a9yee11ll379/+7b2/Oyu5n+zffjiyTURERCkvqruAiIg4sCRYIiKiqARLREQUlWCJiIiiEiwREVFUgiUiIopKsERERFEJloh9IOlISZb0i9W8JK2Q9JCk/9DWb42kFWOsv0TSDyRNkfSrkv5Z0hOStkv6J0kndrDvn4z6vH98jjaiO1PqLiBikpoPPG77+5IOA64FXgYstP1YW7+rgf8h6cN+7tPIZwHXAy8B/h54L3AzcAjwa8BTe9n3dttHlzqYiJJyxhKxb+YDGyS9HPhH4AngjaNCBWAVcBStsABaZxzAW2iF0asAbN9oe7ftnba/Yvvuvez73nKHElFWgiVi3ywApgJ3ANfZ/gPbT4/uZHsnrTORs9ua3wbcb/s7wHeB3ZKukXRqFTqd7DvBEhNWgiVi38wHTgDutv3RvfS9BnirpGnV/NlVG7Z/DPwqYOBTwLCk1ZJetpd9nyVpR9vnowCS/ljSq/b9sCL2n/ISyojuSDoU+AnwZlrXUC6z/bG9rLMF+Avg28D9wEzbPxyj36uBvwMesH3mHvb9y7ab+3koEeMiZywR3XsNsBv4JvA7wF9LeuNe1rmW1pnKWcBXxgoVANv30wqr1+xh3wY2jrVQ0jfbpr8t6aOSNkj6z3upL6KYBEtE9xYA99jeZfsu4H3AzZJm72Gda4HfAN5NNQwGrTMUSX8iaUY1PxM4k9a1mxfa9ybbz7trTNIxwGNt00cDHwZ+Hfit7g4xYt8lWCK6Nx/YMDJj+1rgBmBVdevx89h+CPhn4DBgdduiJ4HXA3dK+hdagXIP8Cd72Pe8Uc+vPCnpCOC1wMjdZK8FVtp+EugHtu7TkUbsg1xjiThASPoA8H3bt1XTj9j+nKS3A0fZ/kTNJcZBImcsEQeOefz8jGUePz+rWtDWHjHucsYSERFF5YwlIiKKSrBERERRCZaIiCjqoHy78THHHONZs2bVXUZExKSxbt26H9nu76TvQRkss2bNotnM2zAiIjol6fud9s1QWEREFJVgiYiIohIsERFRVIIlIiKK6mmwSFosabOkLZKWj7F8kaS7JO2SdEZb+69Xr/4e+fyrpKXVsqslfa9t2fxeHlNERDxXz+4Kk9QHXA68CRgE1kpabbv9K1YfBs4F/rR9Xdtfo/VWVyQdBWwBvtLW5QLbt4xf9RER0ale3m68ENhieyuApJXAEtq+u7t6tTiSnt3Dds4AvmT7p+NXakRE7KteDoUNAI+0zQ9Wbd1aBtw4qu0jku6WdFn11a3PI+k8SU1JzeHh4X3YbUREdKKXwaIx2rp6tbKkY2m9DnxNW/OFwKuBE4GjgD8fa13bV9hu2G7093f08GhEROyDXgbLIDCzbX4GsK3LbbwNuM32MyMNth91y1PAZ2gNuUVERE16GSxrgTmSZks6hNaQ1uq9rDPamYwaBqvOYpAkYCmtr3WNiIia9CxYbO8Czqc1jHUfcLPtTZJWSDoNQNKJkgaBtwKflLRpZH1Js2id8Xxj1Kavl7QR2AgcA/zNeB9LRES8sIPyGyQbjYbzEsqIiM5JWme70UnfPHkfERFFJVgiIqKoBEtERBSVYImIiKISLBERUVSCJSIiikqwREREUb18u3FEvIBV64e4dM1mtu3YyXHTp3HBKcezdMG+vKM1on4JloiarVo/xIW3bmTnM7sBGNqxkwtv3QiQcIlJKUNhETW7dM3mn4XKiJ3P7ObSNZtrqihi/yRYImq2bcfOrtojJroES0TNjps+rav2iIkuwRJRswtOOZ5pU/ue0zZtah8XnHJ8TRVF7J9cvI+o2cgF+twVFgeKBEvEBLB0wUCCJA4YGQqLiIiiEiwREVFUT4NF0mJJmyVtkbR8jOWLJN0laZekM0Yt2y1pQ/VZ3dY+W9Kdkh6QdJOkQ3pxLBFRn1Xrhzjp4tuZvfwLnHTx7axaP1R3SdGmZ8EiqQ+4HDgVmAucKWnuqG4PA+cCN4yxiZ2251ef09raLwEusz0HeBx4V/HiI2LCGHlTwdCOnZifv6kg4TJx9PKMZSGwxfZW208DK4El7R1sP2T7buDZTjYoScAbgVuqpmuApeVKjoiJJm8qmPh6GSwDwCNt84NVW6deLKkp6Q5JI+FxNLDD9q69bVPSedX6zeHh4W5rj4gJIm8qmPh6GSwao81drP9y2w3g94CPSfp33WzT9hW2G7Yb/f39Xew2IiaSvKlg4utlsAwCM9vmZwDbOl3Z9rbq51bg68AC4EfAdEkjz+N0tc2ImHzypoKJr5fBshaYU93FdQiwDFi9l3UAkHSkpEOr6WOAk4B7bRv4GjByB9k5wOeLVx4RE8bSBQNcdPo8BqZPQ8DA9GlcdPq8PGA6gaj1u7lHO5N+E/gY0AdcZfsjklYATdurJZ0I3AYcCfwr8APbJ0j6FeCTtC7qvwj4mO0rq22+gtaNAEcB64Hft/3UnupoNBpuNpvjc5AREQcgSeuqyxF779vLYJkoEiwREd3pJljy5H1ERBSVYImIiKLyduOIiAPcqvVDPf1ahgRLRMQBbOQVOCNvKxh5BQ4wbuGSobCIiANYHa/ASbBERBzA6ngFToIlIuIAVscrcBIsEREHsDpegZOL9xERB7CRC/S5KywiIopZumCgp+9Sy1BYREQUlWCJiIiiEiwREVFUgiUiIopKsERERFEJloiIKCrBEhERRSVYIiKiqJ4Gi6TFkjZL2iJp+RjLF0m6S9IuSWe0tc+X9C1JmyTdLentbcuulvQ9SRuqz/xeHU9ERDxfz568l9QHXA68CRgE1kpabfvetm4PA+cCfzpq9Z8CZ9t+QNJxwDpJa2zvqJZfYPuW8T2CiIjoRC9f6bIQ2GJ7K4CklcAS4GfBYvuhatmz7Sva/m7b9DZJjwH9wA4iImJC6eVQ2ADwSNv8YNXWFUkLgUOAB9uaP1INkV0m6dAXWO88SU1JzeHh4W53GxERHeplsGiMNne1AelY4DrgnbZHzmouBF4NnAgcBfz5WOvavsJ2w3ajv7+/m91GREQXehksg8DMtvkZwLZOV5Z0OPAF4C9s3zHSbvtRtzwFfIbWkFtERNSkl8GyFpgjabakQ4BlwOpOVqz63wZca/uzo5YdW/0UsBS4p2jVERHRlZ4Fi+1dwPnAGuA+4GbbmyStkHQagKQTJQ0CbwU+KWlTtfrbgEXAuWPcVny9pI3ARuAY4G96dUwREfF8sru6zHFAaDQabjabdZcRETFpSFpnu9FJ3zx5HxERRSVYIiKiqARLREQUlWCJiIiiEiwREVFUgiUiIopKsERERFEJloiIKCrBEhERRSVYIiKiqARLREQUlWCJiIiiEiwREVFUgiUiIopKsERERFEJloiIKCrBEhERRfU0WCQtlrRZ0hZJy8dYvkjSXZJ2STpj1LJzJD1Qfc5pa/8lSRurbX5cknpxLLFnq9YPcdLFtzN7+Rc46eLbWbV+qO6SIqJHehYskvqAy4FTgbnAmZLmjur2MHAucMOodY8CPgy8HlgIfFjSkdXiTwDnAXOqz+JxOoTo0Kr1Q1x460aGduzEwNCOnVx468aES8RBopdnLAuBLba32n4aWAksae9g+yHbdwPPjlr3FOCrtrfbfhz4KrBY0rHA4ba/ZdvAtcDScT+S2KNL12xm5zO7n9O285ndXLpmc00VRUQv9TJYBoBH2uYHq7b9WXegmt7rNiWdJ6kpqTk8PNxx0dG9bTt2dtUeEQeWXgbLWNc+vJ/rdrxN21fYbthu9Pf3d7jb2BfHTZ/WVXtEHFh6GSyDwMy2+RnAtv1cd7Ca3pdtxji54JTjmTa17zlt06b2ccEpx9dUUUT0Ui+DZS0wR9JsSYcAy4DVHa67BnizpCOri/ZvBtbYfhR4UtIbqrvBzgY+Px7FR+eWLhjgotPnMTB9GgIGpk/jotPnsXRBpyOfETGZTenVjmzvknQ+rZDoA66yvUnSCqBpe7WkE4HbgCOB35b0V7ZPsL1d0l/TCieAFba3V9PvBa4GpgFfqj5Rs6ULBhIkEQcptW6mOrg0Gg03m826y4iImDQkrbPd6KRvnryPiIiiEiwREVFUgiUiIopKsERERFEJloiIKCrBEhERRSVYIiKiqARLREQUlWCJiIiiEiwREVFUgiUiIorap5dQSloJPFPNPmr7z8qVFBERk9m+vt34W7b/F4CkowvWExERk9y+BssSSc/S+k6U75YsKCIiJrd9vcZyFvAg8LuSPl2wnoiImOS6PmOpvpirD9gA3GL7geJVRUTEpLXXMxZJJ7TP2/7vwMeBJ2mdsXxqnGqLiIhJqJOhsOtGJiT9IYDtH9r+MvBx2+/udGeSFkvaLGmLpOVjLD9U0k3V8jslzara3yFpQ9vnWUnzq2Vfr7Y5suylndYTERHldRIsapv+41HLvtnpjiT1AZcDpwJzgTMlzR3V7V3A47ZfCVwGXAJg+3rb823Pp3V95yHbG9rWe8fIctuPdVpTRESU10mwuG1ao5Z1c/F/IbDF9lbbTwMrgSWj+iwBrqmmbwFOljR6n2cCN3ax34iI6KFOguHfSjpX0gKeHywea4UXMAA80jY/WLWN2cf2LuAJYPRzMm/n+cHymWoY7ENjBBEAks6T1JTUHB4e7qLsiIjoRid3hf0l0ADeCcyQtAm4v/oc08W+xvqFPzqY9thH0uuBn9q+p235O2wPSfoF4HO0hsqufd5G7CuAKwAajUY3gRgREV3Ya7BUv5B/RtIM4LXAPOAfutjXIDCzbX4GsO0F+gxKmgIcAWxvW76MUWcrtoeqn09KuoHWkNvzgiUiInqj6+dYbA/SCoAvdrnqWmCOpNnAEK2Q+L1RfVYD5wDfAs4AbrdtAEkvAt4KLBrpXIXPdNs/kjQVeAvwf7s9poiIKGdfX+nSNdu7JJ0PrKH1gOVVtjdVD1w2ba8GrgSuk7SF1pnKsrZNLAIGbW9tazsUWFOFSh+tUMlzNRERNVJ1QnBQaTQabjabdZcRETFpSFpnu9FJ33wfS0REFJVgiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUUlWCIioqgES0REFJVgiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUUlWCIioqgES0REFJVgiYiIonoaLJIWS9osaYuk5WMsP1TSTdXyOyXNqtpnSdopaUP1+du2dX5J0sZqnY9LUu+OKCIiRutZsEjqAy4HTgXmAmdKmjuq27uAx22/ErgMuKRt2YO251efP2pr/wRwHjCn+iwer2OIiIi96+UZy0Jgi+2ttp8GVgJLRvVZAlxTTd8CnLynMxBJxwKH2/6WbQPXAkvLlx4REZ3qZbAMAI+0zQ9WbWP2sb0LeAI4ulo2W9J6Sd+Q9Gtt/Qf3sk0AJJ0nqSmpOTw8vH9HEhERL6iXwTLWmYc77PMo8HLbC4APAjdIOrzDbbYa7StsN2w3+vv7uyg7IiK60ctgGQRmts3PALa9UB9JU4AjgO22n7L9/wBsrwMeBF5V9Z+xl21GREQP9TJY1gJzJM2WdAiwDFg9qs9q4Jxq+gzgdtuW1F9d/EfSK2hdpN9q+1HgSUlvqK7FnA18vhcHExERY5vSqx3Z3iXpfGAN0AdcZXuTpBVA0/Zq4ErgOklbgO20wgdgEbBC0i5gN/BHtrdXy94LXA1MA75UfSIioiZq3Ux1cGk0Gm42m3WXERExaUhaZ7vRSd88eR8REUUlWCIioqgES0REFJVgiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUUlWCIioqgES0REFJVgiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUX1NFgkLZa0WdIWScvHWH6opJuq5XdKmlW1v0nSOkkbq59vbFvn69U2N1Sfl/buiCIiYrSefee9pD7gcuBNwCCwVtJq2/e2dXsX8LjtV0paBlwCvB34EfDbtrdJeg2wBhhoW+8dtvNdwxERE0Avz1gWAltsb7X9NLASWDKqzxLgmmr6FuBkSbK93va2qn0T8GJJh/ak6oiI6Eovg2UAeKRtfpDnnnU8p4/tXcATwNGj+vwusN72U21tn6mGwT4kSWPtXNJ5kpqSmsPDw/tzHBERsQe9DJaxfuG7mz6STqA1PPaetuXvsD0P+LXqc9ZYO7d9he2G7UZ/f39XhUdEROd6GSyDwMy2+RnAthfqI2kKcASwvZqfAdwGnG37wZEVbA9VP58EbqA15BYRETXpZbCsBeZImi3pEGAZsHpUn9XAOdX0GcDtti1pOvAF4ELb/zTSWdIUScdU01OBtwD3jPNxRETEHvQsWKprJufTuqPrPuBm25skrZB0WtXtSuBoSVuADwIjtySfD7wS+NCo24oPBdZIuhvYAAwBn+rVMUVExPPJHn2Z48DXaDTcbObu5IiITklaZ7vRSd88eR8REUUlWCIioqgES0REFJVgiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUUlWCIioqgES0REFJVgiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUX1NFgkLZa0WdIWScvHWH6opJuq5XdKmtW27MKqfbOkUzrdZimr1g9x0sW3M3v5Fzjp4ttZtX5ovHYVETGp9SxYJPUBlwOnAnOBMyXNHdXtXcDjtl8JXAZcUq07F1gGnAAsBv63pL4Ot7nfVq0f4sJbNzK0YycGhnbs5MJbNyZcIiLG0MszloXAFttbbT8NrASWjOqzBLimmr4FOFmSqvaVtp+y/T1gS7W9Tra53y5ds5mdz+x+TtvOZ3Zz6ZrNpXcVETHp9TJYBoBH2uYHq7Yx+9jeBTwBHL2HdTvZJgCSzpPUlNQcHh7uqvBtO3Z21R4RcTDrZbBojDZ32Kfb9uc32lfYbthu9Pf377HQ0Y6bPq2r9oiIg1kvg2UQmNk2PwPY9kJ9JE0BjgC272HdTra53y445XimTe17Ttu0qX1ccMrxpXcVETHp9TJY1gJzJM2WdAiti/GrR/VZDZxTTZ8B3G7bVfuy6q6x2cAc4NsdbnO/LV0wwEWnz2Ng+jQEDEyfxkWnz2PpgjFH3SIiDmpTerUj27sknQ+sAfqAq2xvkrQCaNpeDVwJXCdpC60zlWXVupsk3QzcC+wC3md7N8BY2xyP+pcuGEiQRER0QK0TgoNLo9Fws9msu4yIiElD0jrbjU765sn7iIgoKsESERFFJVgiIqKoBEtERBSVYImIiKISLBERUVSCJSIiikqwREREUQmWiIgoKsESERFFJVgiIqKoBEtERBSVYImIiKISLBERUVSCJSIiikqwREREUQmWiIgoKsESERFFJVgiIqKog/I77yUNA9/fx9WPAX5UsJxSUld3Uld3Uld3DsS6ftF2fycdD8pg2R+SmrYbddcxWurqTurqTurqzsFeV4bCIiKiqARLREQUlWDp3hV1F/ACUld3Uld3Uld3Duq6co0lIiKKyhlLREQUlWCJiIiiEiwdknSVpMck3VN3Le0kzZT0NUn3Sdok6f111wQg6cWSvi3pO1Vdf1V3TSMk9UlaL+nv666lnaSHJG2UtEFSs+56RkiaLukWSfdXf89+eQLUdHz15zTy+bGkD0yAuv5L9ff9Hkk3Snpx3TUBSHp/VdOmXvw55RpLhyQtAn4CXGv7NXXXM0LSscCxtu+S9AvAOmCp7XtrrkvAYbZ/Imkq8I/A+23fUWddAJI+CDSAw22/pe56Rkh6CGjYnlAP1km6Bvim7U9LOgR4ie0dddc1QlIfMAS83va+Pvhcoo4BWn/P59reKelm4Iu2r66rpqqu1wArgYXA08CXgffafmC89pkzlg7Z/gdge911jGb7Udt3VdNPAvcBA/VWBW75STU7tfrU/r8YSTOA3wI+XXctk4Gkw4FFwJUAtp+eSKFSORl4sM5QaTMFmCZpCvASYFvN9QD8e+AO2z+1vQv4BvA747nDBMsBRNIsYAFwZ72VtFRDThuAx4Cv2p4IdX0M+DPg2boLGYOBr0haJ+m8uoupvAIYBj5TDR9+WtJhdRc1yjLgxrqLsD0E/E/gYeBR4AnbX6m3KgDuARZJOlrSS4DfBGaO5w4TLAcISf8G+BzwAds/rrseANu7bc8HZgALq1Py2kh6C/CY7XV11rEHJ9l+HXAq8L5q+LVuU4DXAZ+wvQD4F2B5vSX9XDU0dxrw2QlQy5HAEmA2cBxwmKTfr7cqsH0fcAnwVVrDYN8Bdo3nPhMsB4DqGsbngOtt31p3PaNVQydfBxbXXMpJwGnVtYyVwBsl/V29Jf2c7W3Vz8eA22iNiddtEBhsO9u8hVbQTBSnAnfZ/mHdhQC/AXzP9rDtZ4BbgV+puSYAbF9p+3W2F9Ea0h+36yuQYJn0qovkVwL32f5o3fWMkNQvaXo1PY3WP7r766zJ9oW2Z9ieRWv45Hbbtf+PEkDSYdXNF1RDTW+mNYRRK9s/AB6RdHzVdDJQ640ho5zJBBgGqzwMvEHSS6p/lyfTuuZZO0kvrX6+HDidcf4zmzKeGz+QSLoR+I/AMZIGgQ/bvrLeqoDW/8LPAjZW1zMA/qvtL9ZYE8CxwDXVHTsvAm62PaFu751gXgbc1vp9xBTgBttfrrekn/lPwPXVsNNW4J011wNAdb3gTcB76q4FwPadkm4B7qI11LSeifNql89JOhp4Bnif7cfHc2e53TgiIorKUFhERBSVYImIiKISLBERUVSCJSIiikqwREREUQmWiIgoKsESERFFJVgiaibpPZL+tpqeKuk6SddUr+qJmHQSLBH1ey1wd/WK+i8BD9s+p3rfVMSkk2CJqN88Wi8G/DrwWdv/rd5yIvZPXukSUTNJj9N6t9Qf2P4/ddcTsb/yEsqIGkmaSesrrx+g9eLOiEkvwRJRr9fS+uKldwN3SFpre33NNUXsl1xjiajXPGCj7UeBPwRuknREzTVF7JcES0S95gEbAWx/FbgZuKrWiiL2Uy7eR0REUTljiYiIohIsERFRVIIlIiKKSrBERERRCZaIiCgqwRIREUUlWCIioqj/D7dRgGTimw80AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "#读取数据\n",
    "train = np.loadtxt(\"hw8_train.dat\")\n",
    "test = np.loadtxt(\"hw8_test.dat\")\n",
    "X_train, y_train = train[:, :-1], train[:, -1]\n",
    "X_test, y_test = test[:, :-1], test[:, -1]\n",
    "\n",
    "class KNeighborsClassifier_():\n",
    "    def __init__(self, n_neighbors):\n",
    "        self.n_neighbors = n_neighbors\n",
    "        \n",
    "        \n",
    "    def fit(self, X, y):\n",
    "        self.X = X\n",
    "        self.y = y\n",
    "        \n",
    "    def predict(self, X):\n",
    "        #计算距离矩阵\n",
    "        d1 = np.sum(X ** 2, axis=1).reshape(-1, 1)\n",
    "        d2 = np.sum(self.X ** 2, axis=1).reshape(1, -1)\n",
    "        dist = d1 + d2 - 2 * X.dot(self.X.T)\n",
    "        \n",
    "        #找到最近的k个点的索引\n",
    "        index = np.argsort(dist, axis=1)[:, :self.n_neighbors]\n",
    "        #计算预测结果\n",
    "        y = np.sign(np.sum(self.y[index], axis=1))\n",
    "        \n",
    "        return y\n",
    "\n",
    "# Q11-12\n",
    "K = [1, 3, 5, 7, 9]\n",
    "Ein = []\n",
    "for k in K:\n",
    "    #训练模型\n",
    "    knn = KNeighborsClassifier_(n_neighbors=k)\n",
    "    knn.fit(X_train, y_train)\n",
    "    #预测结果\n",
    "    y = knn.predict(X_train)\n",
    "    ein = np.mean(y != y_train)\n",
    "    Ein.append(ein)\n",
    "\n",
    "plt.scatter(K, Ein)\n",
    "plt.title(\"$K$ VS $E_{in}$\")\n",
    "plt.xlabel(\"$K$\")\n",
    "plt.ylabel(\"$E_{in}$\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 13-14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY8AAAEZCAYAAABvpam5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAGfpJREFUeJzt3X+UV3d95/HnqwMYQjela6bW8EMwIisJKeR8Jeuq0eaHkI0N2G63SdeYaltMC6tuNE2yxm2lZ38Y2tg9p7TKalq1Io0ac9g2StxWU1M3liEQCUlYCFUzYM1YgzFKDOBr//jeSe4MA8NnmLnfGXw9zpnD937u534/7+HAvObez72fr2wTERFR4ic6XUBEREw8CY+IiCiW8IiIiGIJj4iIKJbwiIiIYgmPiIgolvCIiIhiCY+IGkk/LcmSXlRtS9IaSV+T9HO1fpslrRni+OWS/knSJEmvkvRlSd+V9B1Jfy/p5Scw9lODvt4+Nt9txMhN6nQBEePMIuAJ21+XNA34KPACYIntx2v9/hz4b5J+1wOftL0a+DhwOvBXwG8BtwNTgFcDPxxm7O/Yfv5ofTMRYyVnHhEDLQK2S5oN3At8F7hoUHAA3An8S9qBALTPHIDX0w6clwLY/oTtI7YP2r7b9leHGfuh0ftWIsZOwiNioMXAZOA+4GO232L7mcGdbB+kfUbxplrzvwcesf0A8P+AI5I+IumyKlhOZOyER0wICY+IgRYB5wBftX3rMH0/AvyypKnV9puqNmw/CbwKMPC/gD5JmyS9YJixr5Z0oPY1XA1HkfTzkuaUHhdRIuERUZH0POBlwC8BL5P0juP1t30v0Acsl/Ri4OXAhtr+h23/mu2ZwLnAWcAfDTP2hban176uG8G38hZAIzgu4oQlPCKecy5wBPgS8Abg9yVdNMwxH6V9xnE1cLftbw3VyfYjtCfZzz3O2AZ2DLVT0ipJ90n6iqRXVG2TJf1trc8XJV0B/ALwZ5LeNNR7RYyGhEfEcxYDD9o+bPt+YBVwu6S5xznmo8AlwG9SXbICkPSvJL1T0sxqexZwFe25lGONvdP2UXdjSVpC+xLYK2jPq9xQ7XoZ8HDVpxt4nPYdXttsv9b2R0/s244ol/CIeM4iYHv/RvXDdwNwZ3Xb7lFsfw34MjAN2FTb9T3gAuArkr5POzQeBN55nLEXDnq+43uSfgpYAfxJdUvwj4CD1TELgQeq1z9H+6zlJcCuou86YgSUD4OKGN8krQU+Z/tvJL2P9pnFRknvAXpsf1bSeuCu6pA5toecW4kYLQmPiHFO0ktoXxIT8CXbN1TtrwF+H7gHuBT4VeA02rcQ/x/bx53wjzgZCY+IiCiWOY+IiCiW8IiIiGIJj4iIKHbKrqp75plnes6cOZ0uIyJiQtm6deu3bXcP16/R8JC0DPifQBfwIdv/Y9D+a2k/mHUEeApYafuhat95wAeBM2jf6/5y208fa6w5c+bQ09MzJt9HRMSpStLXT6RfY5etJHUB64DLgAXAVZIWDOq2wfZC24uAW4Bbq2MnAX8BXGv7HOC1wKGmao+IiIGanPNYAuyxvbda4nojsLzeoVqJtN802mv9ALyO9iqnD1T9/tn2kQZqjoiIITQZHjOAx2rbvVXbANUCcI/SPvN4W9X8UsDVR3/eL+l3hhpA0kpJPZJ6+vr6Rrn8iIjo12R4DLVE9FFPKNpeZ/ts2ou/3Vw1T6K9MNx/qP58g6SLhzh2ve2W7VZ397DzPRERMUJNhkcvMKu2PRPYf5z+G2kvCNd/7D22v237B7TX8Dl/TKqMiIhhNRkeW4B5kuZKmgJcycBVSJE0r7Z5ObC7er0ZOE/S6dXk+WvIx3VGRHRMY7fq2j4saTXtIOgCbrO9U9Ia2iuDbgJWS7qE9p1UTwDXVMc+UX0c5xbal7rusv3XTdUeEREDnbILI7ZaLec5j4iIMpK22m4N1y/Lk0RERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRrNDwkLZO0S9IeSTcOsf9aSTskbZd0r6QFVfscSQer9u2SPtBk3RERMdCkpgaS1AWsAy4FeoEtkjbZfqjWbYPtD1T9rwBuBZZV+x61vaipeiMi4tiaPPNYAuyxvdf2M8BGYHm9g+0na5vTADdYX0REnKAmw2MG8Fhtu7dqG0DSKkmPArcAb6vtmitpm6R7JL16qAEkrZTUI6mnr69vNGuPiIiaJsNDQ7QddWZhe53ts4EbgJur5m8Cs20vBq4DNkg6Y4hj19tu2W51d3ePYukREVHXZHj0ArNq2zOB/cfpvxFYAWD7h7b/uXq9FXgUeOkY1RkREcNoMjy2APMkzZU0BbgS2FTvIGlebfNyYHfV3l1NuCPpxcA8YG8jVUdExFEau9vK9mFJq4HNQBdwm+2dktYAPbY3AaslXQIcAp4ArqkOvxBYI+kwcAS41vZ3mqo9IiIGkn1q3tDUarXc09PT6TIiIiYUSVttt4brlyfMIyKiWMIjIiKKJTwiIqJYwiMiIoolPCIioljCIyIiiiU8IiKiWMIjIiKKNfaE+URx57Z9rN28i/0HDnLW9Klcv3Q+KxYftfhvRMSPtYRHzZ3b9nHTHTs4eOgIAPsOHOSmO3YAJEAiImpy2apm7eZdzwZHv4OHjrB2864OVRQRMT4lPGr2HzhY1B4R8eMq4VFz1vSpRe0RET+uEh411y+dz9TJXQPapk7u4vql8ztUUUTE+JQJ85r+SfHcbRURcXwJj0FWLJ6RsIiIGEYuW0VERLGER0REFEt4REREsUbDQ9IySbsk7ZF04xD7r5W0Q9J2SfdKWjBo/2xJT0l6V3NVR0TEYI2Fh6QuYB1wGbAAuGpwOAAbbC+0vQi4Bbh10P73A58d82IjIuK4mjzzWALssb3X9jPARmB5vYPtJ2ub0wD3b0haAewFdjZQa0REHEeT4TEDeKy23Vu1DSBplaRHaZ95vK1qmwbcALz3eANIWimpR1JPX1/fqBUeEREDNRkeGqLNRzXY62yfTTssbq6a3wu83/ZTxxvA9nrbLdut7u7uky44IiKG1uRDgr3ArNr2TGD/cfpvBP60en0B8O8k3QJMB34k6WnbfzwmlUZExHE1GR5bgHmS5gL7gCuBX613kDTP9u5q83JgN4DtV9f6/B7wVIIjIqJzGgsP24clrQY2A13AbbZ3SloD9NjeBKyWdAlwCHgCuKap+iIi4sTJPmra4ZTQarXc09PT6TIiIiYUSVttt4brlyfMIyKiWMIjIiKKJTwiIqJYwiMiIoolPCIioljCIyIiiiU8IiKiWMIjIiKKJTwiIqJYwiMiIoolPCIioljCIyIiiiU8IiKiWMIjIiKKJTwiIqJYwiMiIoolPCIioljCIyIiijUaHpKWSdolaY+kG4fYf62kHZK2S7pX0oKqfUnVtl3SA5Le0GTdERExUGPhIakLWAdcBiwAruoPh5oNthfaXgTcAtxatT8ItKr2ZcAHJU1qqPSIiBikyTOPJcAe23ttPwNsBJbXO9h+srY5DXDV/gPbh6v20/rbIyKiM5r87X0G8Fhtuxe4YHAnSauA64ApwEW19guA24AXAVfXwqR+7EpgJcDs2bNHs/aIiKhp8sxDQ7QddQZhe53ts4EbgJtr7V+xfQ7wcuAmSacNcex62y3bre7u7lEsPSIi6poMj15gVm17JrD/OP03AisGN9p+GPg+cO6oVhcRESesyfDYAsyTNFfSFOBKYFO9g6R5tc3Lgd1V+9z+CXJJLwLmA19rouiIiDhaY3Metg9LWg1sBrqA22zvlLQG6LG9CVgt6RLgEPAEcE11+KuAGyUdAn4E/LbtbzdVe0REDCT71LxxqdVquaenp9NlRERMKJK22m4N1y9PmEdERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0REFEt4REREsYRHREQUG1F4SLqu9nr+6JUTERETQdHCiJKmA+8H5kt6Gvgq8OvAm8egtoiIGKeKwsP2AeDNkpYC3wbOA+4Yi8IiImL8GumS7PfYfhrYOprFRETU3bltH2s372L/gYOcNX0q1y+dz4rFMzpdVjDy8PhDSVNpf4zsI7bXjmJNERHcuW0fN92xg4OHjgCw78BBbrpjB0ACZBwY0YS57VW23wK8A5g+uiVFRMDazbueDY5+Bw8dYe3mXR2qKOpGerfVOyVdDJwGTB7dkiIiYP+Bg0Xt0ayRPuexGXgh8C7g4dErJyKi7azpU4vao1kjDY9fAZYDPwt8+UQPkrRM0i5JeyTdOMT+ayXtkLRd0r2SFlTtl0raWu3bKumiEdYdERPE9UvnM3Vy14C2qZO7uH5pHi0bD0Y6YT7d9i9LmkL7uY9Vwx0gqQtYB1wK9AJbJG2y/VCt2wbbH6j6XwHcCiyjfVvwL9jeL+lc2mc+mTGLOIX1T4rnbqvxaaTh8Yyk84EdwLQTPGYJsMf2XgBJG2mfvTwbHrafrPWfRvtuLmxvq7XvBE6T9DzbPxxh/RExAaxYPCNhMU4Ne9lK0jlDNL8buBhYD/zlCY41A3istt3LEGcPklZJehS4BXjbEO/zS8C2oYJD0kpJPZJ6+vr6TrCsiIgodSJzHh/rfyHpNwBsP10927Ha9mdPcCwN0eajGux1ts8GbgBuHvAG7SB7H/DWoQawvd52y3aru7v7BMuKiIhSJxIe9R/6vz1o398VjNULzKptzwT2H6f/RmDFs0VIM4HPAG+y/WjBuBERMcpOJDzqZweDzx5K7tbaAsyTNLeaaL8S2FTvIGlebfNyYHfVPh34a+Am239fMGZERIyBE/nh/7OSfk3SYo4Oj6MuOx2L7cPAatp3Sj0M3G57p6Q11Z1VAKsl7ZS0HbgOuKa/HXgJ8J7qNt7tkn7mRMeOiIjRJfv4P/8lraS9eu5C4BzgW8Aj1dfVtmePdZEj0Wq13NPT0+kyIiImFElbbbeG6zfsrbq21w9645k8FyYlcx4REXGKKH7Ow3Yv7cnvu0a/nIiImAhG+pBgRIxAPp8iThUJj4iG5PMp4lQy0oURI6JQPp8iTiUJj4iG5PMp4lSS8IhoSD6fIk4lCY+IhuTzKeJUkgnziIbk8yniVJLwiGhQPp8iThW5bBUREcUSHhERUSzhERERxRIeERFRLOERERHFEh4REVEs4REREcUSHhERUazR8JC0TNIuSXsk3TjE/msl7ag+o/xeSQuq9udL+oKkpyT9cZM1R0TE0RoLD0ldwDrgMmABcFV/ONRssL3Q9iLgFuDWqv1p4D3Au5qqNyIijq3JM48lwB7be20/A2wEltc72H6ytjkNcNX+fdv30g6RiIjosCbXtpoBPFbb7gUuGNxJ0irgOmAKcFHJAJJWAisBZs+ePeJCIyLi+Jo889AQbT6qwV5n+2zgBuDmkgFsr7fdst3q7u4eYZkRETGcJsOjF5hV254J7D9O/43AijGtKCIiRqTJ8NgCzJM0V9IU4EpgU72DpHm1zcuB3Q3WFxERJ6ixOQ/bhyWtBjYDXcBttndKWgP02N4ErJZ0CXAIeAK4pv94SV8DzgCmSFoBvM72Q03VHxERz5F91LTDKaHVarmnp6fTZURETCiSttpuDdcvT5hHRESxhEdERBRLeERERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0REFGvy8zwiImKM3LltH2s372L/gYOcNX0q1y+dz4rFM8ZsvIRHRMQEd+e2fdx0xw4OHjoCwL4DB7npjh0AYxYguWwVETHBrd2869ng6Hfw0BHWbt41ZmMmPCIiJrj9Bw4WtY+GhEdExAR31vSpRe2jIeERETHBXb90PlMndw1omzq5i+uXzh+zMTNhHhExwfVPiuduq4iIKLJi8YwxDYvBGr1sJWmZpF2S9ki6cYj910raIWm7pHslLajtu6k6bpekpU3WHRERAzUWHpK6gHXAZcAC4Kp6OFQ22F5oexFwC3BrdewC4ErgHGAZ8CfV+0VERAc0eeaxBNhje6/tZ4CNwPJ6B9tP1janAa5eLwc22v6h7X8E9lTvFxERHdDknMcM4LHadi9wweBOklYB1wFTgItqx9436NjmLu7FMTW9JEJEjA9NnnloiDYf1WCvs302cANwc8mxklZK6pHU09fXd1LFxvD6l0TYd+Ag5rklEe7ctq/TpUXEGGsyPHqBWbXtmcD+4/TfCKwoOdb2etst263u7u6TLDeG04klESJifGgyPLYA8yTNlTSF9gT4pnoHSfNqm5cDu6vXm4ArJT1P0lxgHvAPDdQcx9GJJREiYnxobM7D9mFJq4HNQBdwm+2dktYAPbY3AaslXQIcAp4ArqmO3SnpduAh4DCwyvaRIQeKxpw1fSr7hgiKsVwSISLGB9lHTR2cElqtlnt6ejpdxilt8DLQ0F4S4b//4sJMmkdMUJK22m4N1y9PmMeIdWJJhIgYHxIecVKaXhIhIsaHrKobERHFEh4REVEs4REREcUSHhERUSzhERERxRIeERFRLOERERHFEh4REVEs4REREcUSHhERUSzhERERxRIeERFRLOERERHFEh4REVEs4REREcUSHhERUSzhERERxRoND0nLJO2StEfSjUPsv07SQ5K+KulvJL2otu99kh6svn6lybojImKgxsJDUhewDrgMWABcJWnBoG7bgJbt84BPAbdUx14OnA8sAi4Arpd0RlO1R0TEQE2eeSwB9tjea/sZYCOwvN7B9hds/6DavA+YWb1eANxj+7Dt7wMPAMsaqjsiIgZpMjxmAI/VtnurtmP5deCz1esHgMsknS7pTODngVmDD5C0UlKPpJ6+vr5RKjsiIgab1OBYGqLNQ3aU3gi0gNcA2L5b0suBLwN9wP8FDh/1ZvZ6YD1Aq9Ua8r0jIuLkNXnm0cvAs4WZwP7BnSRdArwbuML2D/vbbf9X24tsX0o7iHaPcb0REXEMTYbHFmCepLmSpgBXApvqHSQtBj5IOzger7V3SXp+9fo84Dzg7sYqj4iIARq7bGX7sKTVwGagC7jN9k5Ja4Ae25uAtcBPAp+UBPAN21cAk4EvVW1PAm+0fdRlq4iIaEaTcx7Yvgu4a1Dbf6m9vuQYxz1N+46riIgYB/KEeUREFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBST7U7XMCYk9QFfP4m3OBP49iiVM5pSV5nUVSZ1lRmPdZ1sTS+y3T1cp1M2PE6WpB7brU7XMVjqKpO6yqSuMuOxrqZqymWriIgolvCIiIhiCY9jW9/pAo4hdZVJXWVSV5nxWFcjNWXOIyIiiuXMIyIiiiU8IiKiWMJjEEm3SXpc0oOdrqWfpFmSviDpYUk7Jb290zUBSDpN0j9IeqCq672drqlOUpekbZL+qtO19JP0NUk7JG2X1NPpevpJmi7pU5Ieqf6dvWIc1DS/+nvq/3pS0js6XReApP9U/Zt/UNInJJ3W6ZoAJL29qmnnWP9dZc5jEEkXAk8BH7V9bqfrAZD0QuCFtu+X9C+ArcAK2w91uC4B02w/JWkycC/wdtv3dbKufpKuA1rAGbZf3+l6oB0eQMv2uHqwTNJHgC/Z/pCkKcDptg90uq5+krqAfcAFtk/m4d/RqGUG7X/rC2wflHQ7cJftP+9wXecCG4ElwDPA54Dfsr17LMbLmccgtv8O+E6n66iz/U3b91evvwc8DMzobFXgtqeqzcnV17j4bUTSTOBy4EOdrmW8k3QGcCHwYQDbz4yn4KhcDDza6eComQRMlTQJOB3Y3+F6AF4G3Gf7B7YPA/cAbxirwRIeE4ykOcBi4CudraStujS0HXgc+LztcVEX8EfA7wA/6nQhgxi4W9JWSSs7XUzlxUAf8GfVZb4PSZrW6aIGuRL4RKeLALC9D/gD4BvAN4Hv2r67s1UB8CBwoaTnSzod+LfArLEaLOExgUj6SeDTwDtsP9npegBsH7G9CJgJLKlOnTtK0uuBx21v7XQtQ3il7fOBy4BV1WXSTpsEnA/8qe3FwPeBGztb0nOqy2hXAJ/sdC0Akn4aWA7MBc4Cpkl6Y2erAtsPA+8DPk/7ktUDwOGxGi/hMUFUcwqfBj5u+45O1zNYdZnji8CyDpcC8Ergimp+YSNwkaS/6GxJbbb3V38+DnyG9vXpTusFemtnjZ+iHSbjxWXA/ba/1elCKpcA/2i7z/Yh4A7g33S4JgBsf9j2+bYvpH35fUzmOyDhMSFUE9MfBh62fWun6+knqVvS9Or1VNr/qR7pbFVg+ybbM23PoX25429td/w3Q0nTqhseqC4LvY72pYaOsv1PwGOS5ldNFwMdvRljkKsYJ5esKt8A/rWk06v/mxfTnofsOEk/U/05G/hFxvDvbdJYvfFEJekTwGuBMyX1Ar9r+8OdrYpXAlcDO6r5BYD/bPuuDtYE8ELgI9WdMD8B3G573NwWOw69APhM++cNk4ANtj/X2ZKe9R+Bj1eXiPYCb+5wPQBU1+4vBd7a6Vr62f6KpE8B99O+LLSN8bNMyaclPR84BKyy/cRYDZRbdSMiolguW0VERLGER0REFEt4REREsYRHREQUS3hERESxhEdERBRLeERERLGER0RDJL1V0geq15MlfUzSR6qlZyImlIRHRHPOA75aLYH+WeAbtq+p1keKmFASHhHNWUh7sbovAp+0/e7OlhMxclmeJKIhkp6gvRbSW2z/707XE3EysjBiRAMkzaL98ca7aS8oGTGhJTwimnEe7Q/n+U3gPklbbG/rcE0RI5Y5j4hmLAR22P4m8BvAX0r6qQ7XFDFiCY+IZiwEdgDY/jxwO3BbRyuKOAmZMI+IiGI584iIiGIJj4iIKJbwiIiIYgmPiIgolvCIiIhiCY+IiCiW8IiIiGL/HyXnMINGcwp+AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Q13-14\n",
    "K = [1, 3, 5, 7, 9]\n",
    "Eout = []\n",
    "for k in K:\n",
    "    #训练模型\n",
    "    knn = KNeighborsClassifier_(n_neighbors=k)\n",
    "    knn.fit(X_train, y_train)\n",
    "    #预测结果\n",
    "    y = knn.predict(X_test)\n",
    "    eout = np.mean(y != y_test)\n",
    "    Eout.append(eout)\n",
    "\n",
    "plt.scatter(K, Eout)\n",
    "plt.title(\"$K$ VS $E_{out}$\")\n",
    "plt.xlabel(\"$K$\")\n",
    "plt.ylabel(\"$E_{out}$\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 15-16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEZCAYAAABiu9n+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAEqNJREFUeJzt3X+w3Xdd5/Hny6SRij9K2yu7JMFUjdVI3Ya9tuiislilFabpjHRpVKgIdlbtgCuLlF2muN3FQeqAMNthrBVt/dFYK1MzTNboKCqKrb2lhVLa0phtyW2QXhdaKhTalPf+cb63PdzcT5J7c+73JPc8HzN37vl8vp9zzvs735vzyuf766SqkCRpMV8z7gIkSccuQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEtIRSrI7yRWL9G9L8s9J1nbtFyb5cJJHknw2yd8n+d7Gaz4rSSX51wU/r1/p9ZGOxNpxFyAdR34X+NUkb62vvlXBK4E/qKoDSb4R+ADwc8ANwDrgB4AvN17zTOCzVXXKypUtLZ8zCU28JM9I8oUkb17Qf3OSnxjqugk4mcGH/vyYZwEvA67rur4DoKqur6onq+qxqvrzqvpY4+3PBD4xqnWRRs2Q0MSrqi8BFwAXz/cluZDBLOD6oXGPMZgdvGro6f8JuKeqPtq1Pwk8meTaJOd1IXIoWzEkdAwzJKSBvwdOS7I2yQnA24A31cF3wLwWuDDJiV37VV0fAFX1eeCFQAG/Bcwl2Znk2Y33PRN4ZZKHh37eOb8wyc8n+Y6RrKG0DPEusNJAkv3ADwE/ClxQVT/SGLcHeAvwj8A9wMaq+kxj7HcCvw/cV1XbFyz7WuBfge+rqpmRrYg0Qs4kpKftAZ7PIADedIhx1zGYQbwS+PNWQABU1T0MDng/b5HFz2Mw47iz9fwkH+p+/2OSdya5I8nrDrMe0sgYEtLT9gBXAh+sqo8cYtx1wDnAzzK0qwkGM4ckb0iyoWtvBLYDNy/yOluBu6pq0TOfkpwKPNT9PgV4K/AfgZcuaa2ko2BISE/bAzybwUyiqaruBz4MPBPYuWDxo8DZwC1JvsAgHD4OvGGRlzoTOGPB9RGPJvmmbvn3AB/rfu+oqkeBKWDvclZOWg6PSUidbjfOD1TVheOuBSDJLwIPAN8C7KuqP0nyCuDkqnrveKvTpHAmIT3tu4E7xl3EkDMYzCTO4Om6tnZ9Ui+cSUidJB8G3l5VC3chSRPLkJAkNbm7SZLUdNzf4O/UU0+tTZs2jbsMSTqu3Hbbbf9SVVOHG3fch8SmTZuYmfFiVUlaiiQPHMk4dzdJkpoMCUlSkyEhSWoyJCRJTYaEJKnJkJAkNRkSkqQmQ0KS1GRISJKaDAlJUpMhIUlqOu7v3bQcb7npTq6/ZR9PVrEmYfvZG/lfF5wx7rIk6ZgzcSHxlpvu5Pdv/tRT7SernmobFJL01SZud9P1t+xbUr8kTbKJC4knG9/E1+qXpEk2cSGxJllSvyRNsokLie1nb1xSvyRNsok7cD1/cNqzmyTp8FLH+b746enp8utLJWlpktxWVdOHGzdxu5skSUfOkJAkNRkSkqQmQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkJkNCktTUa0gkOTfJvUn2JLnsEONenqSSHPbmU5KkldNbSCRZA1wFnAdsAbYn2bLIuG8AXgfc0ldtkqTF9TmTOAvYU1V7q+pxYAewbZFx/xN4B/ClHmuTJC2iz5BYD+wbas92fU9JshXYWFUf6LEuSVJDnyGx2JdIP/WNR0m+BngX8IbDvlBySZKZJDNzc3MjLFGSNKzPkJgFhr9IegOwf6j9DcDzgL9Ocj/wAmDnYgevq+rqqpququmpqakVLFmSJlufIXErsDnJaUnWARcBO+cXVtUjVXVqVW2qqk3AzcD5VeV3k0rSmPQWElV1ALgU2A3cDdxQVXcluSLJ+X3VIUk6cmv7fLOq2gXsWtB3eWPsi/qoSZLU5hXXkqQmQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkJkNCktRkSEiSmgwJSVKTISFJajIkJElNhoQkqcmQkCQ1GRKSpCZDQpLUZEhIkpoMCUlSkyEhSWoyJCRJTYaEJKnJkJAkNRkSkqQmQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkpl5DIsm5Se5NsifJZYss/89J7kxyR5K/S7Klz/okSV+tt5BIsga4CjgP2AJsXyQE/rCqzqiqM4F3AO/sqz5J0sH6nEmcBeypqr1V9TiwA9g2PKCqPj/UfCZQPdYnSVpgbY/vtR7YN9SeBc5eOCjJLwC/BKwDXrzYCyW5BLgE4LnPfe7IC5UkDfQ5k8gifQfNFKrqqqr6NuBNwFsWe6GqurqqpqtqempqasRlSpLm9RkSs8DGofYGYP8hxu8ALljRiiRJh9RnSNwKbE5yWpJ1wEXAzuEBSTYPNV8K3NdjfZKkBXo7JlFVB5JcCuwG1gDvq6q7klwBzFTVTuDSJOcATwCfAy7uqz5J0sH6PHBNVe0Cdi3ou3zo8ev7rEeSdGhecS1JajIkJElNhoQkqcmQkCQ1GRKSpCZDQpLUZEhIkpoMCUlSkyEhSWoyJCRJTYaEJKnJkJAkNRkSkqQmQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkprXLeVKSHcATXfPTVfXLoytJknSsWFZIAP9QVe8GSHLKCOuRJB1DlhsS25J8BdhdVZ8cZUGSpGPHco9JvBL4J+DHk1wzwnokSceQJc8kklwBrAHuAG6sqvtGXpUk6Zhw2JlEku8eblfV5cB7gEcZzCR+a4VqkySN2ZHsbvq9+QdJXgtQVZ+pqj8D3lNVP7tSxUmSxutIQiJDj39+wbIPjbAWSdIx5khCooYeZ8EyL8aTpFXsSA5c/5skPw18lINDog4eLklaLY4kJH4FmAZeDWxIchdwT/dz6sqVJkkat8OGRFVdPdxOsgH4HuAM4G+X8mZJzgXezeAU2muq6u0Llv8S8FrgADAH/ExVPbCU95Akjc6Sr5OoqllgFti1lOclWQNcBfxI9/xbk+ysqk8MDbsdmK6qLyb5OeAdwCuWWqMkaTT6PPB8FrCnqvZW1ePADmDb8ICq+mBVfbFr3gxs6LE+SdICfYbEemDfUHu262t5DfB/FluQ5JIkM0lm5ubmRliiJGlYnyGx8MwoaJwdleSnGBwsv3Kx5VV1dVVNV9X01NTUCEuUJA1b7l1gl2MW2DjU3gDsXzgoyTnAfwd+qKq+3FNtkqRF9DmTuBXYnOS0JOuAi4CdwwOSbAV+Ezi/qh7qsTZJ0iJ6C4mqOgBcCuwG7gZuqKq7klyR5Pxu2JXA1wN/nOSOJDsbLydJ6kGfu5uoql0sOHW2u6vs/ONz+qxHknRo3ntJktRkSEiSmgwJSVKTISFJajIkJElNhoQkqcmQkCQ1GRKSpCZDQpLUZEhIkpoMCUlSkyEhSWoyJCRJTYaEJKnJkJAkNRkSkqQmQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkJkNCktRkSEiSmgwJSVKTISFJajIkJElNhoQkqcmQkCQ1GRKSpCZDQpLU1GtIJDk3yb1J9iS5bJHlP5jkI0kOJHl5n7VJkg7WW0gkWQNcBZwHbAG2J9myYNingJ8G/rCvuiRJbWt7fK+zgD1VtRcgyQ5gG/CJ+QFVdX+37Cs91iVJauhzd9N6YN9Qe7brW7IklySZSTIzNzc3kuIkSQfrMySySF8t54Wq6uqqmq6q6ampqaMsS5LU0mdIzAIbh9obgP09vr8kaYn6DIlbgc1JTkuyDrgI2Nnj+0uSlqi3kKiqA8ClwG7gbuCGqroryRVJzgdI8r1JZoELgd9Mcldf9UmSDtbn2U1U1S5g14K+y4ce38pgN5Qk6RjgFdeSpCZDQpLUZEhIkpoMCUlSkyEhSWoyJCRJTYaEJKnJkJAkNRkSkqQmQ0KS1GRISJKaDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkJkNCktRkSEiSmgwJSVKTISFJajIkJElNhoQkqcmQkCQ1rR13AeN20+0PcuXue9n/8GM856QTeeNLTueCrevHXZYkHRMmOiRuuv1B3vz+O3nsiScBePDhx3jz++8EMCgkiQnf3XTl7nufCoh5jz3xJFfuvndMFUnSsWWiQ2L/w48tqV+SJs1Eh8RzTjpxSf2SNGkmOiTe+JLTOfGENV/Vd+IJa3jjS04fU0WSdGyZ6APX8wenPbtJkhY30SEBg6AwFCRpcb2GRJJzgXcDa4BrqurtC5Z/LXAd8O+B/we8oqru77PGleZ1GZKORt+fIb0dk0iyBrgKOA/YAmxPsmXBsNcAn6uqbwfeBfxaX/X1Yf66jAcffozi6esybrr9wXGXJuk4MI7PkD4PXJ8F7KmqvVX1OLAD2LZgzDbg2u7xjcAPJ0mPNa4or8uQdDTG8RnSZ0isB/YNtWe7vkXHVNUB4BHglIUvlOSSJDNJZubm5lao3NHzugxJR2McnyF9hsRiM4Jaxhiq6uqqmq6q6ampqZEU1wevy5B0NMbxGdJnSMwCG4faG4D9rTFJ1gLfBHy2l+p64HUZko7GOD5D+jy76VZgc5LTgAeBi4CfWDBmJ3Ax8A/Ay4G/qqqDZhLHK6/LkHQ0xvEZkj4/g5P8GPAbDE6BfV9VvS3JFcBMVe1M8gzg94CtDGYQF1XV3kO95vT0dM3MzKx06ZK0qiS5raqmDzeu1+skqmoXsGtB3+VDj78EXNhnTZKktom+d5Mk6dAMCUlSkyEhSWoyJCRJTYaEJKnJkJAkNRkSkqQmQ0KS1GRISJKaDAlJUlOv925aCUnmgAeW+fRTgX8ZYTnHA9d5MrjOq9/Rru+3VNVhv2vhuA+Jo5Fk5khucLWauM6TwXVe/fpaX3c3SZKaDAlJUtOkh8TV4y5gDFznyeA6r369rO9EH5OQJB3apM8kJEmHYEhIkpomNiSSnJvk3iR7klw27npGLcnGJB9McneSu5K8vus/OclfJLmv+/2scdc6aknWJLk9yQe69mlJbunW+Y+SrBt3jaOU5KQkNya5p9ve37fat3OS/9L9XX88yfVJnrHatnOS9yV5KMnHh/oW3a4ZeE/3efaxJM8fVR0TGRJJ1gBXAecBW4DtSbaMt6qROwC8oaq+C3gB8AvdOl4G/GVVbQb+smuvNq8H7h5q/xrwrm6dPwe8ZixVrZx3A39WVd8J/DsG675qt3OS9cDrgOmqeh6wBriI1bedfxc4d0Ffa7ueB2zufi4B3juqIiYyJICzgD1VtbeqHgd2ANvGXNNIVdWnq+oj3eNHGXxwrGewntd2w64FLhhPhSsjyQbgpcA1XTvAi4EbuyGrap2TfCPwg8BvA1TV41X1MKt8OwNrgROTrAW+Dvg0q2w7V9XfAp9d0N3artuA62rgZuCkJP92FHVMakisB/YNtWe7vlUpySZgK3AL8Oyq+jQMggT45vFVtiJ+A/hl4Ctd+xTg4ao60LVX27b+VmAO+J1uF9s1SZ7JKt7OVfUg8OvApxiEwyPAbazu7TyvtV1X7DNtUkMii/StynOBk3w98CfAL1bV58ddz0pK8jLgoaq6bbh7kaGraVuvBZ4PvLeqtgJfYBXtWlpMtx9+G3Aa8BzgmQx2tyy0mrbz4azY3/mkhsQssHGovQHYP6ZaVkySExgExB9U1fu77s/MT0O73w+Nq74V8B+A85Pcz2AX4osZzCxO6nZLwOrb1rPAbFXd0rVvZBAaq3k7nwP836qaq6ongPcD38/q3s7zWtt1xT7TJjUkbgU2d2dDrGNw0GvnmGsaqW5f/G8Dd1fVO4cW7QQu7h5fDPxp37WtlKp6c1VtqKpNDLbpX1XVTwIfBF7eDVtt6/zPwL4kp3ddPwx8glW8nRnsZnpBkq/r/s7n13nVbuchre26E3hVd5bTC4BH5ndLHa2JveI6yY8x+F/mGuB9VfW2MZc0UkleCHwIuJOn98//NwbHJW4AnsvgH9uFVbXw4NhxL8mLgP9aVS9L8q0MZhYnA7cDP1VVXx5nfaOU5EwGB+rXAXuBVzP4D+Cq3c5J/gfwCgZn8d0OvJbBPvhVs52TXA+8iMEtwT8DvBW4iUW2axeW/5vB2VBfBF5dVTMjqWNSQ0KSdHiTurtJknQEDAlJUpMhIUlqMiQkSU2GhCSpyZCQJDUZEpKkJkNCGqEkm5Pcn+Tbu/YJST7a3Z1WOu4YEtIIVdV9DL6g/iVd16XAn1bV7PiqkpZv7eGHSFqijwPnJDmZwRffnD3meqRlcyYhjd4ngdOBXwF+vaq+MN5ypOXz3k3SiHW3aN8P/BPw/VX1lcM8RTpmOZOQRqz7joPPA5cZEDreGRLSyjgB+JtxFyEdLUNCGrHuO8UfKPflahXwmIQkqcmZhCSpyZCQJDUZEpKkJkNCktRkSEiSmgwJSVKTISFJavr/elpwCcBz+yYAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "class RBFNetworkClassifier():\n",
    "    def __init__(self, gamma):\n",
    "        self.gamma = gamma\n",
    "        self.beta = None\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        self.X = X\n",
    "        self.y = y\n",
    "        \n",
    "    def predict(self, X):\n",
    "        #计算距离矩阵\n",
    "        d1 = np.sum(X ** 2, axis=1).reshape(-1, 1)\n",
    "        d2 = np.sum(self.X ** 2, axis=1).reshape(1, -1)\n",
    "        dist = d1 + d2 - 2 * X.dot(self.X.T)\n",
    "        \n",
    "        #计算exp(-gamma*dist)\n",
    "        d = np.exp(-self.gamma * dist)\n",
    "        \n",
    "        #计算预测结果\n",
    "        y = np.sign(np.sum(d * self.y, axis=1))\n",
    "        \n",
    "        return y\n",
    "\n",
    "# Q15-16\n",
    "Gamma = [0.001, 0.1, 1, 10, 100]\n",
    "Ein_rbf = []\n",
    "for gamma in Gamma:\n",
    "    #训练模型\n",
    "    knn = RBFNetworkClassifier(gamma=gamma)\n",
    "    knn.fit(X_train, y_train)\n",
    "    #预测结果\n",
    "    y = knn.predict(X_train)\n",
    "    ein = np.mean(y != y_train)\n",
    "    Ein_rbf.append(ein)\n",
    "\n",
    "plt.scatter(Gamma, Ein_rbf)\n",
    "plt.title(\"$\\gamma$ VS $E_{in}$\")\n",
    "plt.xlabel(\"$\\gamma$\")\n",
    "plt.ylabel(\"$E_{in}$\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 17-18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY8AAAEZCAYAAABvpam5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAFIxJREFUeJzt3X+QXWd93/H3B1kGxTUVxCqtZbkSiRA1dmJ5tsaEHyX8iEyhliYDiWkLLhPqobXHNDgqVsuQ1EwaglJIOnVCXeIE0oDwgEdoKFOlDb+aMDZeRcbCPxTLxsSSHBAxssFZbEt8+8c9a65Wu1o9q917tav3a2ZH9zznOXe/Z85qP3ue59xzUlVIktTiGcMuQJI0/xgekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SI2SbE9y/STt65P8dZLTuuWXJflKkkeTPJLkz5P84yne8zlJKsn3J3y9c673R5qJ04ZdgDQP/SHwn5P8ah15i4a3AH9cVYeSPBv4LPBvgJuB04GXA09M8Z4XAo9U1Y/PXdnS7PHMQ+okeVaSx5NsmtB+a5J/3te0FXguvTAY7/Mc4A3Ax7qmFwBU1Seq6nBVjVXVn1TVnVN8+wuBu2drX6S5ZnhInar6AbABuGK8Lcmb6J01fKKv3xi9s4m39m3+C8C9VfW1bvkvgcNJPprkdV24HMtaDA/NI4aHdKQ/B1YlOS3JYuDXgXfX0XcQ/SjwpiRLuuW3dm0AVNVjwMuAAv4HcCDJtiTPm+L7Xgi8JcnBvq8Pthaf5GeTrGzdTmoV76orHSnJfuCfAD8HbKiq107Rbw/wHuCrwL3Aiqr61hR9Xwj8T+C+qnrzhHXPBL4PvKSqRk+w9j8C3ltV3ziR95Gm45mHdLQ9wEX0guHdx+j3MXpnHG8B/mSq4ACoqnvpTbSfP8nq8+mdoeyaavskV3VzL7cleUmSxUk+37f+i0kuA/4Z8AdJ3jrVe0mzwautpKPtATYDX6iqvzhGv4/RC5ifAn65f0V3pvF64JNVtTfJCuDNwK2TvM9a4K6qmvRKrCQX0xsCewlwLvA7wHuBe7r1y4Bv07u6a2dV/exx7qc0Y555SEfbAzyPXjBMqaoeBL4CnAFsm7D6e8CLgduSPE4vNL4OXDvJW10IXDDh8x3fS/J3u/UbgN/t5l1+CIwBFwDjk/M/Te+s5SeB3S07Ks2UZx7S0b4PbKuqB6brWFWvnKJ9H70rsKZVVVcDVx+jy2J6V3zR9fsMsBoYnx/5BeBzwHn05l6kOeeZh3S0FwF3DLuIPv8duD7JVwCqagvwZWBTkvfRGza7k97lwW9P8ttDq1SnDK+2kibofkm/v6omDkVJ6hgekqRmDltJkpot2Anzs846q1auXDnsMiRpXtmxY8d3qmrZdP0WbHisXLmS0dET+rCuJJ1yknzzePo5bCVJamZ4SJKaGR6SpGaGhySpmeEhSWpmeEiSmhkekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SJKaGR6SpGaGhySpmeEhSWpmeEiSmi3Yx9DOxNad+9i8fTf7D45x9tIlbFy3hg1rlw+7LEk66Rgena0797Hpll2MPXUYgH0Hx9h0yy4AA0SSJnDYqrN5++6ng2Pc2FOH2bx995AqkqSTl+HR2X9wrKldkk5lhkfn7KVLmtol6VRmeHQ2rlvDksWLjmhbsngRG9etGVJFknTycsK8Mz4p7tVWkjQ9w6PPhrXLDQtJOg4OW0mSmhkekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SJKaDTQ8klyaZHeSPUmuO0a/NyapJCPd8sokY0nu6L4+PLiqJUkTDez2JEkWATcArwX2Arcn2VZVd0/odyZwDXDbhLe4v6ouHEixkqRjGuS9rS4G9lTVAwBJtgDrgbsn9Hsf8AHgVwZY29N8FK0kTW+Qw1bLgYf6lvd2bU9LshZYUVWfnWT7VUl2JvlSkpdP9g2SXJlkNMnogQMHmgscfxTtvoNjFD96FO3Wnfua30uSFrJBhkcmaaunVybPAD4EXDtJv4eBc6tqLfAu4ONJnn3Um1XdWFUjVTWybNmy5gJ9FK0kHZ9BhsdeYEXf8jnA/r7lM4HzgS8meRC4BNiWZKSqnqiqvwGoqh3A/cALZrtAH0UrScdnkOFxO7A6yaokpwOXA9vGV1bVo1V1VlWtrKqVwK3AZVU1mmRZN+FOkucDq4EHZrtAH0UrScdnYOFRVYeAq4HtwD3AzVV1V5Lrk1w2zeavAO5M8jXgU8A7quqR2a7RR9FK0vFJVU3fax4aGRmp0dHR5u282krSqSzJjqoama6fj6GdwEfRStL0vD2JJKmZ4SFJamZ4SJKaGR6SpGaGhySpmeEhSWpmeEiSmhkekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SJKaGR6SpGaGhySpmeEhSWpmeEiSmhkekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SJKaGR6SpGaGhySpmeEhSWpmeEiSmhkekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKnZQMMjyaVJdifZk+S6Y/R7Y5JKMtLXtqnbbneSdYOpWJI0mdMG9Y2SLAJuAF4L7AVuT7Ktqu6e0O9M4Brgtr6284DLgRcBZwP/N8kLqurwoOqXJP3IIM88Lgb2VNUDVfUksAVYP0m/9wEfAH7Q17Ye2FJVT1TVN4A93ftJkoZgkOGxHHiob3lv1/a0JGuBFVX12dZtJUmDM8jwyCRt9fTK5BnAh4BrW7fte48rk4wmGT1w4MCMC5UkHdsgw2MvsKJv+Rxgf9/ymcD5wBeTPAhcAmzrJs2n2xaAqrqxqkaqamTZsmWzXL4kadwgw+N2YHWSVUlOpzcBvm18ZVU9WlVnVdXKqloJ3ApcVlWjXb/LkzwzySpgNfDVAdYuSeozsKutqupQkquB7cAi4KaquivJ9cBoVW07xrZ3JbkZuBs4BFzllVaSNDypOmrqYEEYGRmp0dHRYZchSfNKkh1VNTJdPz9hLklqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SJKaGR6SpGaGhySpmeEhSWo2o/BI8q6+12tmrxxJ0nzQdG+rJEvp3TZ9TZIfAHcCvwS8bQ5qkySdpJrCo6oOAm/rniH+HeCngFvmojBJ0slrpnfV/VJV/QDYMZvFSJLmh5mGx39JsoTe0/zurarNs1iTJOkkN6PwqKqrAJKcCVw3qxVJkk56M73a6tokrwaeBSye3ZIkSSe7mQ5bbQcuBH4OuGf2ypEkzQczDY9fBF4I/C1w0+yVI0maD2b6CfOlVfUm4F8D18xiPZKkeWCm4fFkkovoXW11xizWI0maB6YNjyQvmqT5PwKvBm4EPjnbRUmSTm7HM+fxR8BFAEneXlUf6T4guDnJGVX1+JxWKEk66RzPsFX6Xv/bCeu+PIu1SJLmieMJj+p7nQnrvKW7JJ2CjmfY6u8n+VfA1zg6POro7pKkhe54wuPXgBF6t10/J8ldwL3d11lzV5ok6WQ1bXhU1Y39y0nOoXcr9gtwzkOSTknNnzCvqr3AXuBzs1+OJGk+cMJbktTM8JAkNTM8JEnNDA9JUjPDQ5LUzPCQJDUzPCRJzQwPSVIzw0OS1MzwkCQ1MzwkSc0GGh5JLk2yO8meJNdNsv4dSXYluSPJnyU5r2tfmWSsa78jyYcHWbck6UjNN0acqSSLgBuA19K7seLtSbZV1d193T5eVR/u+l8GfBC4tFt3f1VdOKh6JUlTG+SZx8XAnqp6oKqeBLYA6/s7VNVjfYtn4MOmJOmkNMjwWA481Le8t2s7QpKrktwPfAC4pm/VqiQ7k3wpycsn+wZJrkwymmT0wIEDs1m7JKnPIMNj4iNsYZIzi6q6oap+Ang38J6u+WHg3KpaC7wL+HiSZ0+y7Y1VNVJVI8uWLZvF0ufe1p37eOn7P8+q6/4XL33/59m6c9+wS5KkKQ0yPPYCK/qWzwH2H6P/FmADQFU9UVV/073eAdwPvGCO6hy4rTv3semWXew7OEYB+w6OsemWXQaIpJPWIMPjdmB1klVJTgcuB7b1d0iyum/x9cB9XfuybsKdJM8HVgMPDKTqAdi8fTdjTx0+om3sqcNs3r57SBVJmo8GOYIxsKutqupQkquB7cAi4KaquivJ9cBoVW0Drk7yGuAp4LvAFd3mrwCuT3IIOAy8o6oeGVTtc23/wbGmdkmaaHwEY/wP0fERDIANa4+aXj5hAwsPgKr6HBOefV5V7+17/c4ptvs08Om5rW54zl66hH2TBMXZS5cMoRpJ89GxRjDmIjz8hPlJYOO6NSxZvOiItiWLF7Fx3ZohVSRpvhn0CIbhcRLYsHY5v/HzF7B86RICLF+6hN/4+Qvm5K8FSQvTVCMVczWCMdBhK01tw9rlhoWkGdu4bs0Rcx4wtyMYhockLQDjf3xu3r6b/QfHOHvpEjauWzNnf5QaHpK0QAxyBMM5D0lSM8NDktTM8JAkNTM8JEnNDA9JUjPDQ5LUzPCQJDUzPCRJzQwPSVIzw0OS1MzwkCQ1MzwkSc0MD0lSM8NDktTM8JAkNTM8JEnNDA9JUjPDQ5LUzPCQJDUzPCRJzQwPSVIzw0OS1MzwkCQ1MzwkSc0MD0lSM8NDktTM8JAkNTM8JEnNDA9JUjPDQ5LUzPCQJDUzPCRJzQwPSVIzw0OS1Gyg4ZHk0iS7k+xJct0k69+RZFeSO5L8WZLz+tZt6rbbnWTdIOuWJB1pYOGRZBFwA/A64Dzgzf3h0Pl4VV1QVRcCHwA+2G17HnA58CLgUuB3u/eTJA3BIM88Lgb2VNUDVfUksAVY39+hqh7rWzwDqO71emBLVT1RVd8A9nTvJ0kagtMG+L2WAw/1Le8FXjyxU5KrgHcBpwOv6tv21gnbLp9k2yuBKwHOPffcWSlaknS0QZ55ZJK2Oqqh6oaq+gng3cB7Gre9sapGqmpk2bJlJ1SsJGlqgwyPvcCKvuVzgP3H6L8F2DDDbSVJc2iQ4XE7sDrJqiSn05sA39bfIcnqvsXXA/d1r7cBlyd5ZpJVwGrgqwOoWZI0iYHNeVTVoSRXA9uBRcBNVXVXkuuB0araBlyd5DXAU8B3gSu6be9KcjNwN3AIuKqqDg+qdknSkVJ11NTBgjAyMlKjo6PDLkOS5pUkO6pqZLp+fsJcktTM8JAkNTM8JEnNBvkhwXll6859bN6+m/0Hxzh76RI2rlvDhrVHfS5Rkk5Jhscktu7cx6ZbdjH2VO+Crn0Hx9h0yy4AA0SScNhqUpu37346OMaNPXWYzdt3D6kiSTq5GB6T2H9wrKldkk41hsckzl66pKldkk41hsckNq5bw5LFRz4uZMniRWxct2ZIFUnSycUJ80mMT4p7tZUkTc7wmMKGtcsNC0magsNWkqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SJKaGR6SpGaGhySpmeEhSWpmeEiSmhkekqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKlZqmrYNcyJJAeAb85w87OA78xiOfOB+3xqcJ9PDSeyz/+wqpZN12nBhseJSDJaVSPDrmOQ3OdTg/t8ahjEPjtsJUlqZnhIkpoZHpO7cdgFDIH7fGpwn08Nc77PznlIkpp55iFJamZ4SJKaGR4TJLk0ye4ke5JcN+x65kKSFUm+kOSeJHcleWfX/twk/yfJfd2/zxl2rbMpyaIkO5N8tlteleS2bn8/meT0Ydc4m5IsTfKpJPd2x/olp8Ax/uXuZ/rrST6R5FkL7TgnuSnJt5N8va9t0uOanv/a/T67M8lFs1WH4dEnySLgBuB1wHnAm5OcN9yq5sQh4Nqq+kfAJcBV3X5eB/xpVa0G/rRbXkjeCdzTt/ybwIe6/f0u8EtDqWru/A7wv6vqhcBP09v3BXuMkywHrgFGqup8YBFwOQvvOP8hcOmEtqmO6+uA1d3XlcDvzVYRhseRLgb2VNUDVfUksAVYP+SaZl1VPVxVf9G9/h69XyrL6e3rR7tuHwU2DKfC2ZfkHOD1wEe65QCvAj7VdVlo+/ts4BXA7wNU1ZNVdZAFfIw7pwFLkpwG/BjwMAvsOFfVl4FHJjRPdVzXAx+rnluBpUn+wWzUYXgcaTnwUN/y3q5twUqyElgL3AY8r6oehl7AAH9veJXNut8G/j3ww275x4GDVXWoW15ox/r5wAHgD7qhuo8kOYMFfIyrah/wW8Bf0QuNR4EdLOzjPG6q4zpnv9MMjyNlkrYFey1zkr8DfBr4d1X12LDrmStJ3gB8u6p29DdP0nUhHevTgIuA36uqtcDjLKAhqsl04/zrgVXA2cAZ9IZtJlpIx3k6c/ZzbngcaS+wom/5HGD/kGqZU0kW0wuOP66qW7rmb42f0nb/fntY9c2ylwKXJXmQ3lDkq+idiSzthjdg4R3rvcDeqrqtW/4UvTBZqMcY4DXAN6rqQFU9BdwC/AwL+ziPm+q4ztnvNMPjSLcDq7urM06nN9m2bcg1zbpuvP/3gXuq6oN9q7YBV3SvrwA+M+ja5kJVbaqqc6pqJb1j+vmq+hfAF4A3dt0WzP4CVNVfAw8lWdM1vRq4mwV6jDt/BVyS5Me6n/HxfV6wx7nPVMd1G/DW7qqrS4BHx4e3TpSfMJ8gyT+l91fpIuCmqvr1IZc065K8DPh/wC5+NAfwH+jNe9wMnEvvP+KbqmrixNy8luSVwK9U1RuSPJ/emchzgZ3Av6yqJ4ZZ32xKciG9CwROBx4A3kbvD8YFe4yT/CfgF+ldUbgTeDu9Mf4Fc5yTfAJ4Jb3brn8L+FVgK5Mc1y5E/xu9q7P+FnhbVY3OSh2GhySplcNWkqRmhockqZnhIUlqZnhIkpoZHpKkZoaHJKmZ4SFJamZ4SAOQZHWSB5P8ZLe8OMnXurv9SvOO4SENQFXdB9wIrOuargY+U1V7h1eVNHOnTd9F0iz5OvCaJM+l90CiFw+5HmnGPPOQBucvgTXArwG/VVWPD7ccaea8t5U0IN1t8PcD9wM/U1U/nGYT6aTlmYc0IN0zJh4DrjM4NN8ZHtJgLQa+NOwipBNleEgD0j0v/pvlWLEWAOc8JEnNPPOQJDUzPCRJzQwPSVIzw0OS1MzwkCQ1MzwkSc0MD0lSs/8PGt0Ll0stb+kAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Q17-18\n",
    "Gamma = [0.001, 0.1, 1, 10, 100]\n",
    "Eout_rbf = []\n",
    "for gamma in Gamma:\n",
    "    #训练模型\n",
    "    knn = RBFNetworkClassifier(gamma=gamma)\n",
    "    knn.fit(X_train, y_train)\n",
    "    #预测结果\n",
    "    y = knn.predict(X_test)\n",
    "    eout = np.mean(y != y_test)\n",
    "    Eout_rbf.append(eout)\n",
    "\n",
    "plt.scatter(Gamma, Eout_rbf)\n",
    "plt.title(\"$\\gamma$ VS $E_{out}$\")\n",
    "plt.xlabel(\"$\\gamma$\")\n",
    "plt.ylabel(\"$E_{out}$\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 19-20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEZCAYAAABiu9n+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAFD1JREFUeJzt3X2QXXd93/H3p5JI1g9BYAkXyXJEZ0DQ4AcRBUidUB5ShIGJTdu0oa0gTsCZxpPYHY9C5bahJTOdZpS6hMkEj2MT28QxdbBQCEMsPKkJuNSmerLXtiwgPBhLChIFYQM7iSS+/ePeNevV/iSttHvPle/7NXNn7z33d/d8dm3tZ8/vd+7ZVBWSJM3k73UdQJI0vCwJSVKTJSFJarIkJElNloQkqcmSkCQ1WRKSpCZLQiMvyfOSVJIf7z9Okvcl+WqSi6aM25LkfTO8/rIkf5NkYZKfSfK5JN9J8q0k/zvJT53Avr877Xb1/Hy10uws7DqANAQuBr5dVV9LciZwG3Au8Mqq2j9l3C3Af03y3nrmu1DXAbcDZwCfAP4tcCfwHOBngb89zr6/VVXnzNUXI80ljySk3g/qnUnOB+4DvgO8flpBAGwGnk/vBz/QOxIA3kqvWF4CUFV3VNWRqpqoqk9V1UPH2fejc/elSHPLkpBgNbAIuB/4cFX9clX93fRBVTVB7wjhHVM2/wvgsap6EPgCcCTJrUku7RfIiezbktDQsiSk3m/zPwE8VFXXH2fsrcAvJBnrP35HfxtV9STwM0ABfwgcSPLxJOceZ9/rkhyccrseIMmvJXnJyX9Z0qmLF/jTKEvyI8B3gTfSW3P4H1X1/uO85kvAfwQ+DzwGrKiqb8ww7qXAHwNfrKq3H2PfP11VW0/xS5HmhUcSGnUvB44AnwXeBvx2ktcf5zW30TuCWAd8aqaCAKiqx+gVz8uPse8Cxmd6Mslnp9z/fJLrk+xM8hvHySfNGUtCo2418HBVHa6q7cBVwJ1JXnSM19wG/BzwbvpTTdA7ckhybZLz+o9XAG+nt9bR2vcjVXXU2U9JlgD7p9w/B3gv8DrgLbP7EqWTZ0lo1F0M7Jx8UFW3AX8CbO6fDnuUqvoq8DngTODjU556CngV8ECS79Erh4eBa4+x7wumvT/iqSTPBS4EJs+KuhD4SFU9BSwFvnxSX6l0ElyTkIZQkmuAr1XVx/r3v15VdyX5l8Dzq+qDHUfUiPBIQhpOF/DDI4kL+OHRzuop26V555GEJKnJIwlJUpMlIUlqsiQkSU2n/VVglyxZUitXruw6hiSdVrZt2/bNqlp6vHGnfUmsXLmSrVu9ooEkzUaSr53IOKebJElNloQkqcmSkCQ1WRKSpCZLQpLUZElIkposCUlSkyUhSWo67d9Md7I279jDxi272XtwgmWLx1i/dhWXr17edSxJGiojWRKbd+xhw6ZxJg4dAWDPwQk2bOr9mWGLQpJ+aCSnmzZu2f10QUyaOHSEjVt2d5RIkobTSJbE3oMTs9ouSaNqJEti2eKxWW2XpFE1kiWxfu0qxhYteMa2sUULWL92VUeJJGk4jeTC9eTitGc3SdKxjWRJQK8oLAVJOraRnG6SJJ0YS0KS1GRJSJKaBlYSSVYkuTfJriSPJLm6Me61SXb2x/zVoPJJko42yIXrw8C1VbU9ydnAtiT3VNWjkwOSLAb+AHhTVT2e5AUDzCdJmmZgRxJVta+qtvfvPwXsAqafXvSvgE1V9Xh/3P5B5ZMkHa2TNYkkK4HVwAPTnnoJ8Lwkn06yLck7Gq+/MsnWJFsPHDgwv2ElaYQNvCSSnAXcBVxTVU9Oe3oh8JPAW4C1wH9K8pLpn6OqbqyqNVW1ZunSpfOeWZJG1UDfTJdkEb2CuL2qNs0w5Angm1X1PeB7ST4DXAR8YYAxJUl9gzy7KcDNwK6qur4x7M+An02yMMkZwKvorV1IkjowyCOJS4B1wHiSnf1t1wHnA1TVDVW1K8ndwEPAD4CbqurhAWaUJE0xsJKoqvuAnMC4jcDG+U8kSToe33EtSWqyJCRJTZaEJKnJkpAkNVkSkqQmS0KS1GRJSJKaLAlJUpMlIUlqsiQkSU2WhCSpyZKQJDVZEpKkJktCktRkSUiSmiwJSVKTJSFJarIkJElNloQkqcmSkCQ1WRKSpCZLQpLUZElIkposCUlSkyUhSWqyJCRJTZaEJKnJkpAkNVkSkqQmS0KS1DSwkkiyIsm9SXYleSTJ1ccY+1NJjiT554PKJ0k62sIB7uswcG1VbU9yNrAtyT1V9ejUQUkWAL8DbBlgNknSDAZ2JFFV+6pqe//+U8AuYPkMQ38duAvYP6hskqSZdbImkWQlsBp4YNr25cDbgBuO8/ork2xNsvXAgQPzFVOSRt7ASyLJWfSOFK6pqienPf1+4D1VdeRYn6OqbqyqNVW1ZunSpfMVVZJG3iDXJEiyiF5B3F5Vm2YYsgb4SBKAJcCbkxyuqs0DjClJ6htYSaT3k/9mYFdVXT/TmKp60ZTxtwCfsCAkqTuDPJK4BFgHjCfZ2d92HXA+QFUdcx1CkjR4AyuJqroPyCzG/9L8pZEknQjfcS1JarIkJElNloQkqcmSkCQ1WRKSpCZLQpLUZElIkposCUlSkyUhSWqyJCRJTZaEJKnJkpAkNVkSkqQmS0KS1GRJSJKaLAlJUpMlIUlqsiQkSU2WhCSpyZKQJDVZEpKkJktCktRkSUiSmiwJSVKTJSFJalrYdQANv8079rBxy272Hpxg2eIx1q9dxeWrl3cdS9IAWBI6ps079rBh0zgTh44AsOfgBBs2jQNYFNIIcLpJx7Rxy+6nC2LSxKEjbNyyu6NEkgbJktAx7T04Mavtkp5dLAkd07LFY7PaLunZZWAlkWRFknuT7ErySJKrZxjzr5M81L99LslFg8qnma1fu4qxRQuesW1s0QLWr13VUSJJgzTIhevDwLVVtT3J2cC2JPdU1aNTxnwF+MdV9e0klwI3Aq8aYEZNM7k47dlN0mgaWElU1T5gX//+U0l2AcuBR6eM+dyUl9wPnDeofGq7fPVyS0EaUZ2sSSRZCawGHjjGsF8B/qLx+iuTbE2y9cCBA3MfUJIEdFASSc4C7gKuqaonG2NeR68k3jPT81V1Y1Wtqao1S5cunb+wkjTiBvpmuiSL6BXE7VW1qTHmQuAm4NKq+n+DzCdJeqaTKokkHwEO9R/uq6rfPIHXBLgZ2FVV1zfGnA9sAtZV1RdOJpskae6c7JHE/6mq3wNIcs4JvuYSYB0wnmRnf9t1wPkAVXUD8FvAOcAf9DqFw1W15iQzSpJO0cmWxGVJfgBsOdHf+KvqPiDHGfMu4F0nmUmSNMdOduF6HfDXwD9LctMc5pEkDZFZH0kkeR+wANgJfLSqvjjnqSRJQ+G4RxJJfmLq46r6LeADwFP0jiT+cJ6ySZI6diLTTR+evJPkXQBV9Y2quhv4QFW9e77CSZK6dSIlMXWx+demPffZOcwiSRoyJ1ISNeX+9LOTvNS4JD2LncjC9d9P8kvAgxxdEnX0cEnSs8WJlMR/BtYAVwDnJXkEeKx/WzJ/0SRJXTtuSVTVjVMfJzkPuBC4APjMPOWSJA2BWb9PoqqeAJ4APjn3cSRJw8SFZ0lSkyUhSWqyJCRJTZaEJKnJkpAkNVkSkqQmS0KS1GRJSJKaLAlJUpMlIUlqsiQkSU2WhCSpyZKQJDVZEpKkJktCktRkSUiSmiwJSVKTJSFJarIkJElNloQkqWlgJZFkRZJ7k+xK8kiSq2cYkyQfSPKlJA8lecWg8kmSjrZwgPs6DFxbVduTnA1sS3JPVT06ZcylwIv7t1cBH+x/lCR1YGBHElW1r6q29+8/BewClk8bdhlwW/XcDyxO8sJBZZQkPVMnaxJJVgKrgQemPbUc+PqUx09wdJGQ5MokW5NsPXDgwHzFlKSRN/CSSHIWcBdwTVU9Of3pGV5SR22ourGq1lTVmqVLl85HTEkSAy6JJIvoFcTtVbVphiFPACumPD4P2DuIbJKkow3y7KYANwO7qur6xrCPA+/on+X0auA7VbVvUBklSc80yLObLgHWAeNJdva3XQecD1BVNwCfBN4MfAn4PnDFAPNJkqYZWElU1X3MvOYwdUwBVw0mkSTpeAZ5JCGNhM079rBxy272Hpxg2eIx1q9dxeWrjzpJTzotWBLSHNq8Yw8bNo0zcegIAHsOTrBh0ziARaHTktdukubQxi27ny6ISROHjrBxy+6OEkmnxpKQ5tDegxOz2i4NO0tCmkPLFo/Nars07CwJaQ6tX7uKsUULnrFtbNEC1q9d1VEi6dS4cC3NocnFac9u0rOFJSHNsctXL7cU9KzhdJMkqcmSkCQ1WRKSpCZLQpLUZElIkposCUlSkyUhSWqyJCRJTZaEJKnJkpAkNVkSkqQmS0KS1GRJSJKaLAlJUpOXCpfUqc079vj3N4aYJSGpM5t37GHDpnEmDh0BYM/BCTZsGgewKIaE002SOrNxy+6nC2LSxKEjbNyyu6NEms6SkNSZvQcnZrVdg2dJSOrMssVjs9quwbMkJHVm/dpVjC1a8IxtY4sWsH7tqo4SaToXriV1ZnJx2rObhpclIalTl69ebikMsYFNNyX5UJL9SR5uPP/cJH+e5MEkjyS5YlDZJEkzG+SaxC3Am47x/FXAo1V1EfBa4L8nec4AckmSGgZWElX1GeBbxxoCnJ0kwFn9sYcHkU2SNLNhOrvp94GXAXuBceDqqvrBTAOTXJlka5KtBw4cGGRGSRopw1QSa4GdwDLgYuD3k/zYTAOr6saqWlNVa5YuXTrIjJI0UoapJK4ANlXPl4CvAC/tOJMkjbRhKonHgTcAJDkXWAV8udNEkjTiBvY+iSR30DtraUmSJ4D3AosAquoG4LeBW5KMAwHeU1XfHFQ+SdLRBlYSVfX24zy/F3jjgOJIkk7AME03SZKGjCUhSWqyJCRJTZaEJKnJkpAkNVkSkqQmS0KS1GRJSJKaLAlJUpMlIUlqsiQkSU2WhCSpyZKQJDVZEpKkJktCktRkSUiSmgb2R4ckSadu8449bNyym70HJ1i2eIz1a1dx+erl87Y/S0KSThObd+xhw6ZxJg4dAWDPwQk2bBoHmLeicLpJkk4TG7fsfrogJk0cOsLGLbvnbZ+WhCSdJvYenJjV9rlgSUjSaWLZ4rFZbZ8LloQknSbWr13F2KIFz9g2tmgB69eumrd9unAtSaeJycVpz26SJM3o8tXL57UUpnO6SZLUZElIkposCUlSkyUhSWqyJCRJTZaEJKnJkpAkNVkSkqSmVFXXGU5JkgPA107hUywBvjlHcebSMOYaxkxgrtky1+w8W3P9eFUtPd6g074kTlWSrVW1pusc0w1jrmHMBOaaLXPNzqjncrpJktRkSUiSmiwJuLHrAA3DmGsYM4G5ZstcszPSuUZ+TUKS1OaRhCSpyZKQJDWNZEkkWZHk3iS7kjyS5OquMwEk+dEkn0/yYD/Xf+k601RJFiTZkeQTXWeZlOSrScaT7Eyytes8k5IsTvLRJI/1/z/76SHItKr/fZq8PZnkmq5zAST5d/3/5x9OckeSH+06E0CSq/uZHunye5XkQ0n2J3l4yrbnJ7knyRf7H583H/seyZIADgPXVtXLgFcDVyX5hx1nAvhb4PVVdRFwMfCmJK/uONNUVwO7ug4xg9dV1cVDdi777wF3V9VLgYsYgu9bVe3uf58uBn4S+D7wsY5jkWQ58BvAmqp6ObAA+MVuU0GSlwPvBl5J77/hW5O8uKM4twBvmrbt3wN/WVUvBv6y/3jOjWRJVNW+qtrev/8UvX/Ag/t7gA3V893+w0X921CcWZDkPOAtwE1dZxl2SX4MeA1wM0BV/V1VHew21VHeAPx1VZ3K1Qrm0kJgLMlC4Axgb8d5AF4G3F9V36+qw8BfAW/rIkhVfQb41rTNlwG39u/fClw+H/seyZKYKslKYDXwQLdJevpTOjuB/cA9VTUUuYD3A78J/KDrINMU8Kkk25Jc2XWYvn8AHAD+qD89d1OSM7sONc0vAnd0HQKgqvYAvws8DuwDvlNVn+o2FQAPA69Jck6SM4A3Ays6zjTVuVW1D3q/+AIvmI+djHRJJDkLuAu4pqqe7DoPQFUd6U8HnAe8sn/I26kkbwX2V9W2rrPM4JKqegVwKb1pw9d0HYjeb8WvAD5YVauB7zFPUwEnI8lzgJ8H/rTrLAD9ufTLgBcBy4Azk/ybblNBVe0Cfge4B7gbeJDeVPVIGdmSSLKIXkHcXlWbus4zXX964tMcPQ/ZhUuAn0/yVeAjwOuT/HG3kXqqam//43568+uv7DYRAE8AT0w5CvwovdIYFpcC26vqG10H6fs54CtVdaCqDgGbgH/UcSYAqurmqnpFVb2G3nTPF7vONMU3krwQoP9x/3zsZCRLIknozRfvqqrru84zKcnSJIv798fo/eN5rNtUUFUbquq8qlpJb5rif1VV57/pJTkzydmT94E30psi6FRV/Q3w9SSr+pveADzaYaTp3s6QTDX1PQ68OskZ/X+bb2AIFvoBkryg//F84J8yXN+3jwPv7N9/J/Bn87GThfPxSU8DlwDrgPH+/D/AdVX1yQ4zAbwQuDXJAnoFfmdVDc3ppkPoXOBjvZ8rLAT+pKru7jbS034duL0/tfNl4IqO8wDQn1v/J8Cvdp1lUlU9kOSjwHZ60zk7GJ5LYdyV5BzgEHBVVX27ixBJ7gBeCyxJ8gTwXuC/AXcm+RV6RfsL87JvL8shSWoZyekmSdKJsSQkSU2WhCSpyZKQJDVZEpKkJktCktRkSUiSmiwJaY4l+dUkN/TvL0ry4SS39i8FI51WLAlp7l0IPNS/ZPhfAI9X1Tv71yWSTiuWhDT3LqB3MbhPA39aVf+h2zjSyfOyHNIcS/Jtetcg+uWq+vOu80inYlQv8CfNiyQrgO/Su6T0CzuOI50yS0KaWxfS++M07wbuT/J/q2pHx5mkk+aahDS3LgDG+39O8l3A/0zy3I4zSSfNkpDm1gXAOEBV3QPcCXyo00TSKXDhWpLU5JGEJKnJkpAkNVkSkqQmS0KS1GRJSJKaLAlJUpMlIUlq+v9CE8pApVXH/QAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "Created on Fri Apr 19 16:24:00 2019\n",
    "\n",
    "@author: qinzhen\n",
    "\"\"\"\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "X = np.genfromtxt(\"hw8_nolabel_train.dat\")\n",
    "\n",
    "class KMeans_():\n",
    "    def __init__(self, k, D=1e-5):\n",
    "        #聚类数量\n",
    "        self.k = k\n",
    "        #聚类中心\n",
    "        self.cluster_centers_ = []\n",
    "        #聚类结果\n",
    "        self.labels_ = []\n",
    "        #设置阈值\n",
    "        self.D = D\n",
    "        \n",
    "    def fit(self, X):\n",
    "        #数据维度\n",
    "        n, d = X.shape\n",
    "        #聚类标签\n",
    "        labels = np.zeros(n, dtype=int)\n",
    "        #初始中心点\n",
    "        index = np.random.randint(0, n, self.k)\n",
    "        cluster_centers = X[index]\n",
    "        #记录上一轮迭代的聚类中心\n",
    "        cluster_centers_pre = np.copy(cluster_centers)\n",
    "        \n",
    "        while True:\n",
    "            #计算距离矩阵\n",
    "            d1 = np.sum(X ** 2, axis=1).reshape(-1, 1)\n",
    "            d2 = np.sum(cluster_centers ** 2, axis=1).reshape(1, -1)\n",
    "            dist = d1 + d2 - 2 * X.dot(cluster_centers.T)\n",
    "            \n",
    "            #STEP1:找到最近的中心\n",
    "            labels = np.argmin(dist, axis=1)\n",
    "            #STEP2:重新计算中心\n",
    "            for i in range(self.k):\n",
    "                #第i类的索引\n",
    "                index = (labels==i)\n",
    "                #第i类的数据\n",
    "                x = X[index]\n",
    "                #判断是否有点和某聚类中心在一类\n",
    "                if len(x) != 0:\n",
    "                    cluster_centers[i] = np.mean(x, axis=0)\n",
    "                \n",
    "            #计算误差\n",
    "            delta = np.linalg.norm(cluster_centers - cluster_centers_pre)\n",
    "            \n",
    "            if delta < self.D:\n",
    "                break\n",
    "            \n",
    "            cluster_centers_pre = np.copy(cluster_centers)\n",
    "            \n",
    "        self.cluster_centers_ = np.copy(cluster_centers)\n",
    "        self.labels_ = labels\n",
    "        \n",
    "        \n",
    "    def predict(self, X):\n",
    "        #计算距离矩阵\n",
    "        d1 = np.sum(X ** 2, axis=1).reshape(-1, 1)\n",
    "        d2 = np.sum(self.cluster_centers_ ** 2, axis=1).reshape(1, -1)\n",
    "        dist = d1 + d2 - 2 * X.dot(self.cluster_centers_.T)\n",
    "        \n",
    "        #找到最近的中心\n",
    "        self.cluster_centers_ = np.argmin(dist, axis=1)\n",
    "        \n",
    "        return self.cluster_centers_\n",
    "\n",
    "n = X.shape[0]\n",
    "K = [2, 4, 6, 8, 10]\n",
    "Ein = []\n",
    "for k in K:\n",
    "    #训练模型\n",
    "    kmeans = KMeans_(k)\n",
    "    kmeans.fit(X)\n",
    "    #获得标签\n",
    "    label = kmeans.labels_\n",
    "    #获得聚类中心\n",
    "    center = kmeans.cluster_centers_\n",
    "    #计算Ein\n",
    "    ein = 0\n",
    "    for i in range(k):\n",
    "        #计算每一类的误差\n",
    "        ein += np.sum((X[label==i] - center[i]) ** 2)\n",
    "    #计算均值\n",
    "    ein /= n\n",
    "    Ein.append(ein)\n",
    "    \n",
    "plt.scatter(K, Ein)\n",
    "plt.title(\"$K$ VS $E_{in}$\")\n",
    "plt.xlabel(\"$K$\")\n",
    "plt.ylabel(\"$E_{in}$\")\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
